#include <vector>
#include <map>
using namespace std;

// sorted with greatest first.
template <class T>
class heap {
 public:
  const T* top() const;
  T pop();
  bool remove(const T&);
  void insert(const T&);
  bool update(const T& old, const T& replacement);
 private:
  map<T,int> index_;
  vector<T> heap_;

  bool remove(int pos);
  void bubble(int pos);
  void bubble_up(int pos);
  void bubble_down(int pos);

  inline void swap(int pos1, int pos2) {
    index_[heap_[pos1]] = pos2;
    index_[heap_[pos2]] = pos1;
    T temp = heap_[pos1];
    heap_[pos1] = heap_[pos2];
    heap_[pos2] = temp;
  }
  inline int left(int pos) { return 2*pos + 1; }
  inline int right(int pos) { return 2*pos + 2; }
  inline int parent(int pos) { return (pos - 1)/2; }
  inline bool is_leaf(int pos) { return left(pos) >= heap_.size(); }
  // cannot be called on a leaf;
  inline int max_child(int pos) {
    if (right(pos) >= heap_.size())
      return left(pos);
    if (heap_[right(pos)] < heap_[left(pos)]) {
      return left(pos);
    } else {
      return right(pos);
    }
  }
};   
